package com.study.homework;

import com.sun.istack.internal.NotNull;

import java.util.*;

/**
 * 关于数组和链表的几个必知必会的代码实现
 * 数组
 * 实现一个支持动态扩容的数组
 * 实现一个大小固定的有序数组，支持动态增删改操作
 * 实现两个有序数组合并为一个有序数组
 * <p>
 * 链表
 * 实现单链表、循环链表、双向链表，支持增删操作
 * 实现单链表反转
 * 实现两个有序的链表合并为一个有序链表
 * 实现求链表的中间结点
 * <p>
 * 对应的 LeetCode 练习题（@Smallfly 整理）
 * 数组
 * Three Sum（求三数之和）
 * https://leetcode-cn.com/problems/3sum/
 * <p>
 * Majority Element（求众数）
 * https://leetcode-cn.com/problems/majority-element/
 * <p>
 * Missing Positive（求缺失的第一个正数）
 * https://leetcode-cn.com/problems/first-missing-positive/
 * <p>
 * 链表
 * Linked List Cycle I（环形链表）
 * https://leetcode-cn.com/problems/linked-list-cycle/
 * <p>
 * Merge k Sorted Lists（合并 k 个排序链表）
 * https://leetcode-cn.com/problems/merge-k-sorted-lists/
 */
public class Day1 {

    public static void main(String[] args) {
        // 实现一个支持动态扩容的数组
//        autoGrowArray();
        //实现一个大小固定的有序数组，支持动态增删改操作
//        sortArray();
        //实现两个有序数组合并为一个有序数组
//        mergeArray();

        //单链表翻转
//        linkReverse();

        //实现两个有序的链表合并为一个有序链表
//        mergeLinkedList();

        //实现求链表的中间结点
//        findMid();

        //三数之和  先排序 再遍历 高低指针轮流遍历 注意跳过相同数字
//        System.out.println(threeSum(new int[]{-2, -3, 0, 0, -2}));

        //Missing Positive（求缺失的第一个正数）
//        firstMissingPositive(new int[]{1, 2, -1, 0, 1000});
//        firstMissingPositive1(new int[]{1, 2, -1, 0, 1000});


        //Majority Element（求众数）
//        System.out.println(majorityElement(new int[]{1, 2, 3, 2, 3, 3, 3}));
//        System.out.println(majorityElement2(new int[]{1, 2, 3, 2, 3, 3, 3}));

        //环形链表
//        Node node = Node.from(new int[]{1, 2, 3, 4, 5, 6});
//        System.out.println(node.toString());


        //合并 k 个排序链表
        Node node = Node.from(new int[]{1, 2, 3, 4, 5, 6});
        Node node1 = Node.from(new int[]{2, 5, 7, 8, 9, 10, 15, 16});
        Node node2 = Node.from(new int[]{7, 11, 21, 30, 32, 35});
        Node node3 = Node.from(new int[]{7, 9, 14, 15, 26});
        Node node4 = Node.from(new int[]{1, 5, 6, 8, 11, 51});

        //循环合并
//        Node listNode = mergeKLists(new Node[]{node, node1, node2, node3, node4});
        //类似归并排序的合并 减少大量不必要的数组遍历
        Node listNode = mergeKLists1(new Node[]{node, node1, node2, node3, node4});

        System.out.println(listNode.toString());
    }

    public static Node mergeKLists1(Node[] lists) {
        if (lists == null || lists.length <= 0) {
            return null;
        }
        if (lists.length == 1) {
            return lists[0];
        }
        return mergeKLists(lists, 0, lists.length - 1);
    }

    private static Node mergeKLists(Node[] lists, int l, int h) {
        if (l >= h) {
            return lists[l];
        }

        int m = l + ((h - l) >> 1);
        Node lNode = mergeKLists(lists, l, m);
        Node rNode = mergeKLists(lists, m + 1, h);

        return mergeLinkedList(lNode, rNode);
    }

    public static Node mergeKLists(Node[] lists) {
        Node header = new Node(-1);
        header.next = lists[0];
        for (int i = 1; i < lists.length; i++) {
            mergeLinkedList(header.next, lists[i]);
        }
        return header.next;
    }

    public static boolean hasCycle(Node head) {
        if (head == null || head.next == null) {
            return false;
        }
        if (head == head.next) {
            return true;
        }
        Node s = head;
        Node f = head;

        do {
            s = s.next;
            f = f.next.next;
        } while (f != null && f.next != null && s != f);

        return s == f;
    }


    public static int majorityElement2(int[] nums) {
        int count = 0;
        int result = nums[0];

        for (int num : nums) {
            if (count == 0) result = num;
            count += (result == num) ? 1 : -1;
        }
        return result;
    }

    public static int majorityElement(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }

        HashMap<Integer, Integer> map = new HashMap<>();
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            int value = nums[i];
            Integer count = map.get(value);
            if (count == null) {
                map.put(value, 1);
            } else {
                if (++count >= (len / 2 + 1)) {
                    return value;
                }
                map.put(value, count);
            }
        }
        return nums[0];
    }


    public static int firstMissingPositive(int[] nums) {
        int n = nums.length;

        // 基本情况
        int contains = 0;
        for (int i = 0; i < n; i++)
            if (nums[i] == 1) {
                contains++;
                break;
            }

        if (contains == 0)
            return 1;

        // sNums = [1]
        if (n == 1)
            return 2;

        // 用 1 替换负数，0，
        // 和大于 n 的数
        // 在转换以后，sNums 只会包含
        // 正数
        for (int i = 0; i < n; i++)
            if ((nums[i] <= 0) || (nums[i] > n))
                nums[i] = 1;

        // 使用索引和数字符号作为检查器
        // 例如，如果 sNums[1] 是负数表示在数组中出现了数字 `1`
        // 如果 sNums[2] 是正数 表示数字 2 没有出现
        for (int i = 0; i < n; i++) {
            int a = Math.abs(nums[i]);
            // 如果发现了一个数字 a - 改变第 a 个元素的符号
            // 注意重复元素只需操作一次
            if (a == n)
                nums[0] = -Math.abs(nums[0]);
            else
                nums[a] = -Math.abs(nums[a]);
        }

        // 现在第一个正数的下标
        // 就是第一个缺失的数
        for (int i = 1; i < n; i++) {
            if (nums[i] > 0)
                return i;
        }

        if (nums[0] > 0)
            return n;

        return n + 1;
    }

    public static int firstMissingPositive1(int[] nums) {
        HashSet<Integer> set = new HashSet<>();

        for (int num : nums) {
            set.add(num);
        }
        int i = 1;
        while (set.contains(i)) {
            i++;
        }
        return i;
    }

    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int g = target - nums[i];
            if (map.get(g) != null) {
                return new int[]{map.get(g), i};
            }
            map.put(nums[i], i);
        }

        return null;
    }

    private static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);

        int li;
        int hi;
        for (int i = 0; i < nums.length - 1; i++) {

            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            li = i + 1;
            hi = nums.length - 1;
            while (li < hi && nums[li] <= nums[hi]) {
                int num = nums[i];
                int l = nums[li];
                int h = nums[hi];
                if (num + l + h == 0) {
                    list.add(Arrays.asList(num, l, h));
                    if (l == h) {
                        break;
                    }
                    while (hi >= li && nums[li] == nums[li + 1]) {
                        li++;
                    }
                    li++;
                } else if (num + l + h > 0) {
                    while (hi >= li && nums[hi] == nums[hi - 1]) {
                        hi--;
                    }
                    hi--;
                } else {
                    while (hi > li && nums[li] == nums[li + 1]) {
                        li++;
                    }
                    li++;
                }
            }
        }
        return list;
    }

    private static void findMid() {
        Node b = Node.from(new int[]{1, 6, 9, 12, 21, 28});
        Node mid = findMid(b);
        System.out.println(mid.data);
    }

    private static Node findMid(Node node) {
        Node slow = node;
        Node fast = node;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    private static void mergeLinkedList() {
        Node a = Node.from(new int[]{1, 3, 4, 5, 9, 14});
        Node b = Node.from(new int[]{1, 6, 9, 12, 21, 28});
        Node result = mergeLinkedList(a, b);
        System.out.println(result.toString());
    }

    private static Node mergeLinkedList(Node a, Node b) {
        Node header = new Node(1);

        Node cur = header;
        while (a != null && b != null) {
            if (a.data <= b.data) {
                cur.next = a;
                a = a.next;
            } else {
                cur.next = b;
                b = b.next;
            }
            cur = cur.next;
        }

        if (a != null) {
            cur.next = a;
        }
        if (b != null) {
            cur.next = b;
        }

        Node result = header.next;
        header.next = null;
        return result;
    }

    private static void linkReverse() {
        Node node = Node.from(new int[]{1, 2, 3, 4, 5, 6});
        System.out.println(node.toString());

        Node reverse = reverseLink(node);
        System.out.println(reverse.toString());
    }

    @NotNull
    private static Node reverseLink(Node node) {
        if (node == null || node.next == null) {
            return node;
        }

        Node next = node.next;
        node.next = null;

        while (next != null) {
            Node temp = next.next;
            next.next = node;
            node = next;
            next = temp;
        }
        return node;
    }

    private static void mergeArray() {
        int[] a = {1, 2, 3, 7, 9};
        int[] b = {4, 5, 6, 8, 10};
        int[] c = mergeArray(a, b);
        System.out.println(Arrays.toString(c));
    }

    private static int[] mergeArray(int[] a, int[] b) {
        if (a == null || a.length <= 0) {
            return b;
        }
        if (b == null || b.length <= 0) {
            return a;
        }


        int[] c = new int[a.length + b.length];

        int i = 0;
        int ai = 0;
        int bi = 0;

        while (ai < a.length && bi < b.length) {
            if (a[ai] <= b[bi]) {
                c[i] = a[ai];
                ai++;
            } else {
                c[i] = b[bi];
                bi++;
            }
            i++;
        }

        while (ai < a.length) {
            c[i] = a[ai];
            ai++;
            i++;
        }
        while (bi < b.length) {
            c[i] = b[bi];
            bi++;
            i++;
        }
        return c;
    }

    private static void sortArray() {
        MySortArray array = new MySortArray(3);
        array.add(1);
        array.add(12);
        array.add(123);
//        array.add(1234);

        array.update(2, 321);
        array.remove(1);

        System.out.println(array.get(1));
        System.out.println(array.toString());
    }

    private static void autoGrowArray() {
        MyArrayList list = new MyArrayList();
        for (int i = 11; i < 80; i++) {
            list.add(i);
        }
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    }
}
